struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// https://leetcode.cn/problems/swap-nodes-in-pairs/
class Solution1//循环解法
{
public:
    ListNode* swapPairs(ListNode* head) 
    {
        if(!head || !head->next) return head;
        ListNode* l1 = head;
        ListNode* next = l1->next;
        head = next;
        ListNode* nnext = nullptr;
        ListNode* prev = new ListNode(0);
        prev->next = l1;
        while(l1 && next)
        {
            nnext = next->next;

            prev->next = l1->next;
            l1->next = nnext;
            next->next = l1;

            prev = l1;
            l1 = nnext;
            if(nnext)
            next = l1->next;
        }
        return head;
    }
};

//https://leetcode.cn/problems/reorder-list/
class Solution2 {
public:
    void reorderList(ListNode* head) 
    {
        if(!head || !head->next||!head->next->next) return;
        ListNode* slow = head, *fast = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        ListNode* left = slow, *ret = slow->next;
        ListNode* right = ret->next;
        left->next = nullptr;
        left = nullptr;

        while(ret)//三指针法链表调头
        {
            right = ret->next;
            ret->next = left;
            left = ret;
            ret = right;
        }

        while(left)
        {
            fast = head->next;
            right = left->next;

            left->next = head->next;
            head->next = left;

            head = fast;
            left = right;
        }
    }
};


//https://leetcode.cn/problems/merge-k-sorted-lists/
class Solution3 {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists)
    {
        if(lists.size() == 0) return nullptr;
        for(int i = 2; i < lists.size() * 2; i *= 2)
        {
            for(int j = 0; j < lists.size(); j += i)
            {
                ListNode* left = lists[j];
                if(j + i/2 < lists.size())
                {
                    ListNode* right = lists[j + i/2];
                    ListNode* prev= new ListNode();
                    lists[j] = prev;
                    while(left && right)
                    {
                        if(left->val <= right->val)
                        {
                            prev->next = left;
                            prev = left;
                            left = left->next;
                        }
                        else
                        {
                            prev->next = right;
                            prev = right; 
                            right = right->next;
                        }
                    }
                    if(left) prev->next = left;
                    else prev->next = right;
                    lists[j] = lists[j]->next;
                }
            }
        }
        return lists[0];
    }
};